# 637.二叉树的层平均值
# 给定一个非空二叉树的根节点root, 以数组的形式返回每一层节点的平均值。与实际答案相差10^-5以内的答案可以被接受。
#
#
# 示例1：
# 输入：root = [3, 9, 20, null, null, 15, 7]
# 输出：[3.00000, 14.50000, 11.00000]
# 解释：第0层的平均值为3, 第1层的平均值为14.5, 第2层的平均值为11 。因此返回[3, 14.5, 11] 。
#
# 示例2：
# 输入：root = [3,9,20,15,7]
# 输出：[3.00000,14.50000,11.00000]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def averageOfLevels(self, root):
        from collections import deque
        que = deque()
        res = []
        if not root:
            return res
        que.append(root)
        while que:
            tmp = []
            size = len(que)
            for i in range(size):
                node = que.popleft()
                tmp.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            ave = sum(tmp) / size
            res.append(ave)
        return res


if __name__ == '__main__':
    a32 = TreeNode(7)
    a31 = TreeNode(15)
    a21 = TreeNode(9)
    a22 = TreeNode(20,a31,a32)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    res = tmp.averageOfLevels(a11)
    print(res)

